package graphmanip.collapsing;


import graphmanip.CollapsingMethod;

import java.awt.Point;
import java.util.ArrayList;


import commonfunctions.Functions;
import commonfunctions.Matrix;

public class SmarterHungarianCollapsing extends CollapsingMethod 
{
	public ArrayList<ArrayList<Integer>> collapse(Matrix weights) 
	{
		ArrayList<ArrayList<Integer>> nodesFromTo = new ArrayList<ArrayList<Integer>>();
		ArrayList<ArrayList<Integer>> nodesToFrom = new ArrayList<ArrayList<Integer>>();
		for (int i = 0; i < weights.length(); i++)
			nodesToFrom.add(new ArrayList<Integer>());
		for (int i = 0; i < weights.length(); i++)
		{
			ArrayList<Integer> toAdd = new ArrayList<Integer>();
			for (int j = 0; j < weights.length(); j++)
			{
				if (weights.get(i, j) > 0.0)
				{
					toAdd.add(j);
					nodesToFrom.get(j).add(i);
				}
			}
			nodesFromTo.add(toAdd);
		}
		int[] nodeGrouping = new int[weights.length()];
		for (int i = 0; i < nodeGrouping.length; i++)
			nodeGrouping[i] = -1;
		boolean notAllPositive = true;
		int groupToSet = 0;
		while (notAllPositive)
		{
			ArrayList<Integer> toSet = new ArrayList<Integer>();
			for (int i = 0; i < nodeGrouping.length; i++)
			{
				if(nodeGrouping[i] == -1)
				{
					toSet.add(i);
					break;
				}
			}
			
			while (toSet.size() > 0)
			{
				int thisVal = toSet.remove(0);
				if (nodeGrouping[thisVal] == -1)
				{
					nodeGrouping[thisVal] = groupToSet;
					for (int i = 0; i < nodesToFrom.get(thisVal).size(); i++)
					{
						if (nodeGrouping[nodesToFrom.get(thisVal).get(i)] != groupToSet)
							toSet.add(nodesToFrom.get(thisVal).get(i));
					}
					for (int i = 0; i < nodesFromTo.get(thisVal).size(); i++)
					{
						if (nodeGrouping[nodesFromTo.get(thisVal).get(i)] != groupToSet)
							toSet.add(nodesFromTo.get(thisVal).get(i));
					}
				}
			}
			
			groupToSet++;
			
			notAllPositive = false;
			for (int i = 0; i < nodeGrouping.length; i++)
			{
				if (nodeGrouping[i] == -1)
				{
					notAllPositive = true;
					break;
				}
			}
		}
		int[] nodeTimeValues = Functions.getTimeMappings(weights);
		
		HungarianAlgo h = new HungarianAlgo(weights);
		int maxTimeValue = 0;
		for (int i = 0; i < nodeTimeValues.length; i++)
		{
			if (nodeTimeValues[i] > maxTimeValue)
				maxTimeValue = nodeTimeValues[i];
		}
		ArrayList<ArrayList<Integer>> toReturn = new ArrayList<ArrayList<Integer>>();
		for (int i = 0; i < maxTimeValue; i++)
		{
			ArrayList<Point> edgesToTest = new ArrayList<Point>();
			ArrayList<Point> edgesAround = new ArrayList<Point>();
			ArrayList<Point> negativeEdgesToTest = new ArrayList<Point>();
			double valueToBeat = 0.0;
			for (int j = 0; j < weights.length(); j++)
			{
				for (int k = 0; k < weights.length(); k++)
				{
					if (nodeTimeValues[k] > i && nodeTimeValues[j] < i + 1 && 
							!(nodeTimeValues[k] == i + 1 && nodeTimeValues[j] == i))
						edgesAround.add(new Point(j, k));
					else if (nodeTimeValues[k] == i + 1 && nodeTimeValues[j] == i && weights.get(j, k) > 0.0)
						edgesToTest.add(new Point(j, k));
					else if (nodeTimeValues[k] == i + 1 && nodeTimeValues[j] == i)
						negativeEdgesToTest.add(new Point(j, k));
				}
			}
			int maxEdgeAround = 0;
			for (int j = 0; j < edgesAround.size(); j++)
				maxEdgeAround = (weights.get(edgesAround.get(j).x, edgesAround.get(j).y) > 
									weights.get(edgesAround.get(maxEdgeAround).x, 
									edgesAround.get(maxEdgeAround).y))?j:maxEdgeAround;
			int maxToTest = 0;
			for (int j = 0; j < edgesToTest.size(); j++)
				maxToTest = (weights.get(edgesToTest.get(j).x, edgesToTest.get(j).y) > 
									weights.get(edgesToTest.get(maxToTest).x, 
									edgesToTest.get(maxToTest).y))?j:maxToTest;
			
			if ((edgesAround.size() > 0 && edgesToTest.size() > 0 &&
					weights.get(edgesAround.get(maxEdgeAround).x, edgesAround.get(maxEdgeAround).y)
					> weights.get(edgesToTest.get(maxToTest).x, edgesToTest.get(maxToTest).y)) ||
				(edgesToTest.size() == 0 && edgesAround.size() > 0))
			{
				Point maxPoint = edgesAround.get(maxEdgeAround);
				edgesAround.addAll(edgesToTest);
				edgesAround.addAll(negativeEdgesToTest);
				edgesToTest = new ArrayList<Point>();
				for (int k = 0; k < edgesAround.size(); k++)
				{
					if (nodeTimeValues[edgesAround.get(k).x] == nodeTimeValues[maxPoint.x] && 
						nodeTimeValues[edgesAround.get(k).y] == nodeTimeValues[maxPoint.y] && 
						weights.get(edgesAround.get(k).x, edgesAround.get(k).y) > 0.0)
					{
							edgesToTest.add(edgesAround.remove(k));
							k--;
					}
				}
			}
			
			ArrayList<Point> originalPoints = h.hungarianAlgorithm(edgesToTest);
			
			for (int j = 0; j < edgesAround.size(); j++)
			{
				if (nodeGrouping[edgesAround.get(j).x] == nodeGrouping[edgesAround.get(j).y] && 
						edgesToTest.size() > 0 && 
						nodeGrouping[edgesAround.get(j).x] == nodeGrouping[edgesToTest.get(0).x])
				{
					if (weights.get(edgesAround.get(j).x, edgesAround.get(j).y) > 0.0)
						valueToBeat += weights.get(edgesAround.get(j).x, edgesAround.get(j).y);
					else 
						valueToBeat -= weights.get(edgesAround.get(j).x, edgesAround.get(j).y);
				}
			}
			double valueToBeLessThan = 0.0;
			for (int j = 0; j < originalPoints.size(); j++)
				valueToBeLessThan += weights.get(originalPoints.get(j).x, originalPoints.get(j).y);
			valueToBeLessThan -= valueToBeat;
			for (int j = 0; j < originalPoints.size(); j++)
			{
				Point thisPoint = originalPoints.get(j);
				ArrayList<Integer> pointsList = new ArrayList<Integer>();
				pointsList.add(thisPoint.x);
				pointsList.add(thisPoint.y);
				double thisPointVal = weights.get(thisPoint.x, thisPoint.y);
				if (thisPointVal > valueToBeat && !toReturn.contains(pointsList))
				{
					weights.set(0.0, thisPoint.x, thisPoint.y);
					ArrayList<Point> newPoints = h.hungarianAlgorithm(originalPoints);
					double thisVal = 0.0;
					for (int k = 0; k < newPoints.size(); k++)
						thisVal += weights.get(newPoints.get(k).x, newPoints.get(k).y);
					if (thisVal < valueToBeLessThan)
					{
						ArrayList<Integer> toAdd = new ArrayList<Integer>();
						toAdd.add(thisPoint.x);
						toAdd.add(thisPoint.y);
						toReturn.add(toAdd);
					}
					weights.set(thisPointVal, thisPoint.x, thisPoint.y);
				}
			}
		}
		return toReturn;
	}

}
